#include <cstdio>

long long x, y, p;

long long f(long long x, long long y, long long p) {
	if(0 == y) {
		return 1 % p;
	} else if(y % 2 == 0){
		long long tmp = f(x, y/2, p);
		return tmp * tmp % p;
	} else {
		long long tmp = f(x, y/2, p);
		return tmp*tmp % p * x % p;
	}
}

int main()
{
	int t;
	scanf("%d", &t);
	
	while(t--) {
		scanf("%lld%lld%lld", &x, &y, &p);
		printf("%lld\n", f(x, y, p));
	}

	return 0;
}